Abstract: This paper presents CSPR, a compressive sensing based approach for path reconstruction in wireless sensor networks. By viewing the whole network as a path representation space, an arbitrary routing path can be represented by a path vector in the space. As path length is usually much smaller than the network size, such path vectors are sparse, i.e., the majority of elements are zeros. By encoding sparse path representation into packets, the path vector can be recovered from a small amount of packets using compressive sensing technique. CSPR formalizes the sparse path representation and enables accurate and efficient per-packet path reconstruction. CSPR is invulnerable to network dynamics and lossy links due to its distinct design. A set of optimization techniques are further proposed to improve the design. We evaluate CSPR in both testbed-based experiments and large scale trace-driven simulations. Evaluation results show that CSPR achieves high path recovery accuracy and outperforms the state-of the- art approaches in various network settings.

Keywords: Packet path reconstruction; wireless sensor networks; compressive sensing; bloom filter.